package com.kevin.Code.DP;

import java.util.Arrays;

/**
 * @author Vinlee Xiao
 * @Classname CoinChange2
 * @Description Leetcode 518 中等难度 动态规划 不同与Leetcode 322
 * @Date 2021/9/22 16:52
 * @Version 1.0
 */
public class CoinChange2 {
    public static void main(String[] args) {
        CoinChange2 coinChange2 = new CoinChange2();
        int[] nums = new int[]{1, 2, 5};
        int i = coinChange2.change(5, nums);
        System.out.println(i);
    }


    /**
     * 因为外层循环是遍历数组 \textit{coins}coins 的值，内层循环是遍历不同的金额之和，
     * 在计算 \textit{dp}[i]dp[i] 的值时，可以确保金额之和等于 ii 的硬币面额的顺序，由于顺序确定，因此不会重复计算不同的排列。
     *
     * @param amount
     * @param coins
     * @return
     */
    public int change(int amount, int[] coins) {

        //动态转移数组
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, 0);

        //初始化
        dp[0] = 1;
        //初始化
//        for (int i = 0; i < coins.length; i++) {
//            dp[coins[i]] = 1;
//        }


        for (int i = 0; i < coins.length; i++) {

            for (int j = coins[i]; j <= amount; j++) {

                if (coins[j] <= i) {
                    dp[j] = dp[j] + dp[j - coins[i]];
                }
            }
        }


        return dp[amount];
    }

}
